#!/usr/bin/env python3

"""
Given an input string(s) and (p), implement wildcard pattern matching with 
support for '?' and '*'
- '?' Matches any single characters
- '*' Matches any sequence of characters (including the empty sequence)
"""

class Solution:
    def isMatch(self, s, p):
        s_index = 0
        p_index = 0
        p_star_index = -1
        s_star_index = -1
        while s_index < len(s):
            s_ch = s[s_index]
            p_ch = p[p_index] if p_index < len(p) else None
            if p_ch == s_ch or p_ch == '?':
                s_index += 1
                p_index += 1
            elif p_ch == '*':
                p_star_index = p_index
                p_index += 1
                s_star_index = s_index
            elif p_star_index != -1:
                p_index = p_star_index + 1
                s_star_index += 1
                s_index = s_star_index
            else:
                return False
        while p_index < len(p):
            p_ch = p[p_index]
            if p_ch != '*':
                return False
            p_index += 1
        else:
            return True
if __name__ == '__main__':
    s = Solution()
    assert s.isMatch('aaaa', '***a')
    assert not s.isMatch('ab', '*a')
    assert not s.isMatch('a', 'aa')
    assert not s.isMatch('aa', 'a')
    assert s.isMatch('aa', '*')
    
